package com.suanfa;


import java.util.ArrayList;
import java.util.Stack;

public class LianBiao
{
    //输入一个链表，反转链表后，输出新链表的表头
    //1,2,3   3,2,1
    private static class ListNode
    {
        int data;
        ListNode next = null;

        ListNode(int data)
        {
            this.data = data;
        }


    }

    //head指向头结点
    public static ListNode ReverseList(ListNode head)
    {
        Stack<ListNode> stack = new Stack<>();
        //把链表节点全部摘掉放到栈中
        while (head != null)
        {
            stack.push(head);
            head = head.next;
        }
        if (stack.isEmpty())
        {
            return null;
        }
        //首先出栈的构成新的头结点
        ListNode node = stack.pop();
        ListNode dummy = node;
        //栈中的结点全部出栈，然后重新连成一个新的链表
        while (!stack.isEmpty())
        {
            //新出栈的结点
            ListNode tempnode = stack.pop();
            node.next = tempnode;
            node = node.next;

        }
        //最后一个结点就是反转前的头结点，一定要让他的next等于空，否则会构成环
        node.next = null;
        return dummy;
    }

    //递归的思想
    public static ListNode ReverseList2(ListNode head)
    {
        if (head == null || head.next == null)
        {
            return head;
        }
        //除去头结点后的下一个
        ListNode newhead_tail = head.next;
        //头结点为空即变成尾结点
        head.next = null;
        ListNode newHead = ReverseList(newhead_tail);
        //反转后变成尾结点
        newhead_tail.next = head;
        return newHead;
    }

    //头插法
    public static ListNode ReverseList3(ListNode head)
    {
        //新的链表节点的头
        ListNode newhead = null;
        while (head != null)
        {
            ListNode p = head.next;
            head.next = newhead;
            newhead = head;
            head = p;
        }
        return newhead;
    }


    //输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
    //{67,0,24,58}  [58,24,0,67]
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode)
    {
        //使用递归
//        ArrayList<Integer> ret = new ArrayList<>();
//        if (listNode != null)
//        {
//            ret.addAll(printListFromTailToHead(listNode.next));
//            ret.add(listNode.data);
//        }
//        return ret;

        //使用栈
        Stack<Integer> stack = new Stack<>();
        while (listNode != null)
        {
            stack.add(listNode.data);
            listNode = listNode.next;
        }
        ArrayList<Integer> ret = new ArrayList<>();
        while (!stack.isEmpty()) ret.add(stack.pop());
        return ret;
    }


    //输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
    //{1,3,5},{2,4,6}      {1,2,3,4,5,6}
    //递归
    public ListNode Merge(ListNode list1, ListNode list2)
    {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.data <= list2.data)
        {
            list1.next = Merge(list1.next, list2);
            return list1;
        }
        else
        {
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }
}
